package org.huangrui.javase.basic;

/**
 * 求素数
 * @Author hr
 * @Create 2025-11-06 21:53
 **/
public class T06PrimeNumber {
    public static int[] generatePrimes(int n) {
        //素数：大于1的自然数中，只能被1和它本身整除的数
        boolean[] isPrime = new boolean[n + 1];

        // 初始化所有数为素数
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // 使用埃拉托斯特尼筛选法（简称埃氏筛法）筛选素数
        /*
        去除2的倍数：4,6,8,10,12.....
        去除3的倍数：9,12,15，....
        去除5的倍数：25,30,....
         */
        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        // 计算素数的数量
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }

        // 创建素数数组
        int[] primes = new int[count];
        int index = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes[index++] = i;
            }
        }
        return primes;
    }

    public static void main(String[] args) {
        int n = 100; // 示例输入
        int[] primes = generatePrimes(n);
        for (int prime : primes) {
            System.out.print(prime + " ");
        }
    }
}
